package sort;

import java.util.*;

/**
 * 冒泡排序
 *
 * @author RunningShrimp
 * @date 2021/6/15  10:32
 * @see <a href=""></a>
 */
@SuppressWarnings("unchecked")
public class BubbleSort<E extends Comparable<E>> extends BaseSort<E> {
    @Override
    public void sort(E[] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 1; j < array.length; j++) {
                if (less(array[j - 1], array[j])) {
                    exchange(array, j - 1, j);
                }
            }
        }
    }

    /**
     * 性能更优的冒泡排序
     * 冒泡排序第1次遍历后会将最大值放到最右边，这个最大值也是全局最大值。
     * 标准冒泡排序的每一次遍历都会比较全部的元素，虽然最右侧的值已经是最大值了。
     * 改进之后，每次遍历后的最大值，次大值，等等会固定在右侧，避免了重复比较
     * @param list
     */
    public void sort(List<E> list) {
        E[] array = (E[]) new Comparable[list.size()];
        for (int i = 0; i < list.size(); i++) {
            array[i] = list.get(i);
        }

        for (int i = array.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (less(array[j], array[j + 1])) {
                    exchange(array, j +1 , j);
                }
            }
        }
        list.clear();
        Collections.addAll(list, array);
    }

    public static void main(String[] args) {
        Integer[] array = BaseSort.generateArray(5, 10);
        BubbleSort<Integer> sort = new BubbleSort<>();
        List<Integer> list = new ArrayList<>(array.length);
        Collections.addAll(list, array);

        System.out.println("排序前：");
        sort.show(array);
        sort.sort(array);
        System.out.println("排序后");
        sort.show(array);
        System.out.println("是否有序：" + sort.isSorted(array));
        sort.sort(list);
        System.out.println(list);
    }
}
